public class MergeIntervals {
    /**
     * 以数组 intervals 表示若干个区间的集合，
     * 其中单个区间为 intervals[i] = [starti, endi] 。
     * 请你合并所有重叠的区间，并返回一个不重叠的区间数组，
     * 该数组需恰好覆盖输入中的所有区间。
     * 链接：https://leetcode-cn.com/problems/merge-intervals
     * @param intervals
     * @return
     */
    public static int[][] merge(int[][] intervals) {
        //先排序
        for (int i=0;i<intervals.length;i++){
            for (int j=0;j<intervals.length-i-1;j++){
                if (intervals[j][0]>intervals[j+1][0]){
                    int[] temp = intervals[j+1];
                    intervals[j+1] = intervals[j];
                    intervals[j] = temp;
                }
            }
        }
        int[][] ans = new int[10000][];
        ans[0] = intervals[0];
        int j=0;
        for (int i=1;i<intervals.length;i++){
            int len = intervals[i][1]-intervals[i][0]+ans[j][1]-ans[j][0];
            if (intervals[i][1]-ans[j][0]<=len){
                ans[j] = new int[]{ans[j][0],intervals[i][1]};
            }else {
                ans[j+1] = intervals[i];
                j++;
            }
        }
        int[][] new_ans = new int[j][];
        for (int i=0;i<j+1;i++){
            new_ans[i] = ans[i];
        }
        return new_ans;


    }

    public static void main(String[] args) {
        int arr[][] = {{1,3},{2,6},{8,10},{15,18}};
        merge(arr);
    }
}
